home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / ZSORTDD.ZIP / ZSORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-10-21  |  41.3 KB  |  1,327 lines
  1. /* clip.c
  2.  
  3.    Win32 program to demonstrate z-sorted spans.
  4.  
  5.    Derived from the VC++ generic sample application.
  6.    Tested with VC++ 2.0 running on Windows NT 3.5.
  7.  
  8.    Note: in this implementation, polygon faces must not be
  9.    interpenetrating. Also, correct sorting is not guaranteed
  10.    if two polygonal objects butt up against each other. In other
  11.    words, each polygonal object must be made of a continuous,
  12.    non-self-intersecting skin, and polygonal objects must not
  13.    interpenetrate or touch in order for proper sorting to result.
  14.    More complex, slower sorting is required to make those cases
  15.    work reliably.
  16.  
  17.    Note: polygon processing could be considerably more efficient
  18.    if polygons shared common edges and edges shared common vertices.
  19.    Also, indirection to vertices could be used to avoid having to
  20.    copy all the vertices during every clip test. Outcode-type
  21.    testing could be used to determine completely clipped or
  22.    unclipped polygons ahead of time, avoiding the need to clip and
  23.    copy entirely for such polygons. Outcode-type tests work best in
  24.    viewspace, with the frustum normalized so that the field of view
  25.    is 90 degrees, so simple compares, rather than dot products, can
  26.    be used to categorize points with respect to the frustum. See
  27.    _Computer Graphics_, by Foley & van Dam, or _Procedural Elements
  28.    of Computer Graphics_, by Rogers, for further information.
  29.  
  30.   **Altered to use DirectDraw by Keith Harrison Oct 96**
  31.   **Compiled with Watcom 10.6 for Windows 95/NT**
  32.  
  33. */
  34.  
  35. #include <windows.h>    // required for all Windows applications
  36. #include <stdlib.h>
  37. #include <stdio.h>
  38. #include <math.h>
  39.  
  40. #include "zsort.h"              // specific to this program
  41. #include "ddraw.h"
  42.  
  43. #define INITIAL_DIB_WIDTH       640 // initial dimensions of DIB
  44. #define INITIAL_DIB_HEIGHT      480 //  into which we'll draw
  45.  
  46. #define MAX_POLY_VERTS      8       // assumes polygons have no more than
  47. //  four sides and are clipped a maximum of four times by frustum.
  48. //  Must be increased for more sides or more clip planes
  49. #define MAX_SCREEN_HEIGHT   2048
  50. #define MOVEMENT_SPEED      3.0
  51. #define VMOVEMENT_SPEED     3.0
  52. #define MAX_MOVEMENT_SPEED  30.0
  53. #define PI                  3.141592
  54. #define ROLL_SPEED          (PI/20.0)
  55. #define PITCH_SPEED         (PI/20.0)
  56. #define YAW_SPEED           (PI/20.0)
  57. #define MAX_COORD           0x4000
  58. #define NUM_FRUSTUM_PLANES  4
  59. #define CLIP_PLANE_EPSILON  0.0001
  60. #define MAX_SPANS           10000
  61. #define MAX_SURFS           1000
  62. #define MAX_EDGES           5000
  63.  
  64.  
  65. typedef struct {
  66.   double v[3];
  67. } point_t;
  68.  
  69. typedef struct {
  70.   double x, y;
  71. } point2D_t;
  72.  
  73. typedef struct {
  74.   int x, y;
  75.   int count;
  76.   int color;
  77. } span_t;
  78.  
  79. typedef struct {
  80.   double distance;
  81.   point_t normal;
  82. } plane_t;
  83.  
  84. typedef struct {
  85.   int color;
  86.   int numverts;
  87.   point_t verts[MAX_POLY_VERTS];
  88.   plane_t plane;
  89. } polygon_t;
  90.  
  91. typedef struct surf_s {
  92.   struct surf_s *pnext, *pprev;
  93.   int color;
  94.   int visxstart;
  95.   double zinv00, zinvstepx, zinvstepy;
  96.   int state;
  97. } surf_t;
  98.  
  99. typedef struct {
  100.   int numverts;
  101.   point2D_t verts[MAX_POLY_VERTS];
  102. } polygon2D_t;
  103.  
  104. typedef struct convexobject_s {
  105.   struct convexobject_s *pnext;
  106.   point_t center;
  107.   int numpolys;
  108.   polygon_t *ppoly;
  109. } convexobject_t;
  110.  
  111. typedef struct edge_s {
  112.   int x;
  113.   int xstep;
  114.   int leading;
  115.   surf_t *psurf;
  116.   struct edge_s *pnext, *pprev;
  117.   struct edge_s *pnextremove;
  118. } edge_t;
  119.  
  120. //DirectDraw stuff.
  121. LPDIRECTDRAW pDirectDraw = NULL;
  122. DDSURFACEDESC ddSurfaceDesc, ddBackBuffer;
  123. LPDIRECTDRAWSURFACE pDDSurface, pDDBackBuffer;
  124. LPDIRECTDRAWPALETTE pDDPalette;  //Pointer to DirectDraw palette.
  125. PALETTEENTRY palDDPalette[256];  //Hold our palette
  126.  
  127. HINSTANCE hInst;  // current instance
  128. char szAppName[] = "Clip";  // The name of this application
  129. char szTitle[] = "3D clipping demo";  // The title bar text
  130. HPALETTE hpalold, hpalDIB;
  131. HWND hwndOutput;
  132. int DIBWidth, DIBHeight;
  133. int DIBPitch;
  134. double roll, pitch, yaw;
  135. double currentspeed;
  136. point_t currentpos;
  137. double fieldofview, xcenter, ycenter;
  138. double xscreenscale, yscreenscale, maxscale;
  139. double maxscreenscaleinv;
  140. int numobjects;
  141. double speedscale = 1.0;
  142. plane_t frustumplanes[NUM_FRUSTUM_PLANES];
  143.  
  144. double mroll[3][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  145. double mpitch[3][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  146. double myaw[3][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  147. point_t vpn, vright, vup;
  148. point_t xaxis = {1, 0, 0};
  149. point_t zaxis = {0, 0, 1};
  150.  
  151. polygon_t polys0[] = {
  152.   {
  153.     15, 4, { {-10, 10, -10}, {10, 10, -10}, {10, -10, -10}, {-10, -10, -10}},
  154.     {10, {0, 0, -1}}
  155.   },
  156.   {
  157.     14, 4, { {10, 10, -10}, {10, 10, 10}, {10, -10, 10}, {10, -10, -10}},
  158.     {10, {1, 0, 0}}
  159.   },
  160.   {
  161.     13, 4, { {10, 10, 10}, {-10, 10, 10}, {-10, -10, 10}, {10, -10, 10}},
  162.     {10, {0, 0, 1}}
  163.   },
  164.   {
  165.     12, 4, { {-10, 10, 10}, {-10, 10, -10}, {-10, -10, -10}, {-10, -10, 10}},
  166.     {10, {-1, 0, 0}}
  167.   },
  168.   {
  169.     11, 4, { {-10, 10, -10}, {-10, 10, 10}, {10, 10, 10}, {10, 10, -10}},
  170.     {10, {0, 1, 0}}
  171.   },
  172.   {
  173.     10, 4, { {-10, -10, -10}, {10, -10, -10}, {10, -10, 10}, {-10, -10, 10}},
  174.     {10, {0, -1, 0}}
  175.   },
  176. };
  177.  
  178. polygon_t polys1[] = {
  179.   {
  180.     1, 4,
  181.     {
  182.       {-200, 0, -200}, {-200, 0, 200},
  183.       {200, 0, 200}, {200, 0, -200}
  184.     }, {0, {0, 1, 0}}
  185.   },
  186. };
  187.  
  188. polygon_t polys2[] = {
  189.   {
  190.     6, 4, { {0, 10, 0}, {20, 10, 0}, {10, 10, -10}, {0, 10, -10}},
  191.     {10, {0, 1, 0}}
  192.   },
  193.   {
  194.     6, 4, { {-10, 10, 10}, {0, 10, 10}, {0, 10, 0}, {-10, 10, 0}},
  195.     {10, {0, 1, 0}}
  196.   },
  197.   {
  198.     6, 4, { {0, 10, 0}, {0, 10, -10}, {-10, 10, -10}, {-10, 10, 0}},
  199.     {10, {0, 1, 0}}
  200.   },
  201.   {
  202.     5, 4, { {0, -10, 0}, {0, -10, -10}, {10, -10, -10}, {20, -10, 0}},
  203.     {10, {0, -1, 0}}
  204.   },
  205.   {
  206.     5, 4, { {-10, -10, 10}, {-10, -10, 0}, {0, -10, 0}, {0, -10, 10}},
  207.     {10, {0, -1, 0}}
  208.   },
  209.   {
  210.     5, 4, { {-10, -10, 0}, {-10, -10, -10}, {0, -10, -10}, {0, -10, 0}},
  211.     {10, {0, -1, 0}}
  212.   },
  213.   {
  214.     4, 4, { {-10, 10, -10}, {10, 10, -10}, {10, -10, -10}, {-10, -10, -10}},
  215.     {10, {0, 0, -1}}
  216.   },
  217.   {
  218.     3, 4, { {10, 10, -10}, {20, 10, 0}, {20, -10, 0}, {10, -10, -10}},
  219.     {14.14, {0.707, 0, -0.707}}
  220.   },
  221.   {
  222.     2, 4, { {20, 10, 0}, {0, 10, 0}, {0, -10, 0}, {20, -10, 0}},
  223.     {0, {0, 0, 1}}
  224.   },
  225.   {
  226.     9, 4, { {0, 10, 0}, {0, 10, 10}, {0, -10, 10}, {0, -10, 0}},
  227.     {0, {1, 0, 0}}
  228.   },
  229.   {
  230.     15, 4, { {0, 10, 10}, {-10, 10, 10}, {-10, -10, 10}, {0, -10, 10}},
  231.     {10, {0, 0, 1}}
  232.   },
  233.   {
  234.     14, 4, { {-10, 10, 10}, {-10, 10, -10}, {-10, -10, -10}, {-10, -10, 10}},
  235.     {10, {-1, 0, 0}}
  236.   },
  237. };
  238.  
  239. extern convexobject_t objecthead;
  240.  
  241. convexobject_t objects[] = {
  242.   {&objects[1], {-50, 0, 70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  243.   {&objects[2], {0, 20, 70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  244.   {&objects[3], {50, 0, 70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  245.   {&objects[4], {-50, 0, -70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  246.   {&objects[5], {0, 20, -70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  247.   {&objects[6], {50, 30, -70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  248.   {&objects[7], {-50, 15, 0}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  249.   {&objects[8], {50, 15, 0}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  250.   {&objects[9], {0, 50, 0}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  251.   {&objects[10], {-100, 100, 115}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  252.   {&objects[11], {-100, 150, 120}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  253.   {&objects[12], {100, 200, 100}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  254.   {&objects[13], {100, 100, 100}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  255.   {&objecthead, {0, -20, 0}, sizeof(polys1) / sizeof(polys1[0]), polys1},
  256. };
  257.  
  258. // Head and tail for the object list
  259. convexobject_t objecthead = {&objects[0]};
  260.  
  261. // Span, edge, and surface lists
  262. span_t spans[MAX_SPANS];
  263. edge_t edges[MAX_EDGES];
  264. surf_t surfs[MAX_SURFS];
  265.  
  266. // Bucket list of new edges to add on each scan line
  267. edge_t newedges[MAX_SCREEN_HEIGHT];
  268.  
  269. // Bucket list of edges to remove on each scan line
  270. edge_t *removeedges[MAX_SCREEN_HEIGHT];
  271.  
  272. // Head and tail for the active edge list
  273. edge_t edgehead;
  274. edge_t edgetail;
  275.  
  276. // Edge used as sentinel of new edge lists
  277. edge_t maxedge = {0x7FFFFFFF};
  278.  
  279. // Head/tail/sentinel/background surface of active surface stack
  280. surf_t surfstack;
  281.  
  282. // pointers to next available surface and edge
  283. surf_t *pavailsurf;
  284. edge_t *pavailedge;
  285.  
  286. int currentcolor;
  287.  
  288. void UpdateWorld(void);
  289.  
  290. /////////////////////////////////////////////////////////////////////
  291. // WinMain
  292. /////////////////////////////////////////////////////////////////////
  293. int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
  294.         LPSTR lpCmdLine, int nCmdShow)
  295. {
  296.   MSG msg;
  297.   HANDLE hAccelTable;
  298.  
  299.   if (!hPrevInstance) {  // Other instances of app running?
  300.     if (!InitApplication(hInstance))
  301.       return(FALSE);  // Exits if unable to initialize
  302.   }
  303.  
  304.   // Perform initializations that apply to a specific instance
  305.   if (!InitInstance(hInstance,nCmdShow)) return(FALSE);
  306.  
  307.   hAccelTable = LoadAccelerators(hInstance, szAppName);
  308.  
  309.   // Acquire and dispatch messages until a WM_QUIT message is
  310.   // received
  311.   for (;;) {
  312.     if (PeekMessage(&msg,NULL,0,0,PM_REMOVE)) {
  313.       do {
  314.         if (msg.message == WM_QUIT) goto Done;
  315.         if (!TranslateAccelerator(msg.hwnd,hAccelTable, &msg)) {
  316.           TranslateMessage(&msg);  // xlates virt keycodes
  317.           DispatchMessage(&msg);  // Dispatches msg to window
  318.         }
  319.       } while (PeekMessage(&msg,NULL,0,0,PM_REMOVE));
  320.     }
  321.     UpdateWorld(); // Update the world
  322.   }
  323.  
  324. Done:
  325.   //Release our DirectDraw object (also resets video mode)
  326.   if (pDirectDraw != NULL) IDirectDraw_Release(pDirectDraw);
  327.     
  328.   return(msg.wParam);  // Returns the value from PostQuitMessage
  329.  
  330.   lpCmdLine;  // This will prevent 'unused formal parameter' warnings
  331. }
  332.  
  333. /////////////////////////////////////////////////////////////////////
  334. // InitApplication
  335. /////////////////////////////////////////////////////////////////////
  336. BOOL InitApplication(HINSTANCE hInstance)
  337. {
  338.   WNDCLASS wc;
  339.  
  340.   // Fill in window class structure with parameters that
  341.   // describe the main window.
  342.   wc.style = CS_HREDRAW | CS_VREDRAW;
  343.   wc.lpfnWndProc = (WNDPROC)WndProc;
  344.   wc.cbClsExtra = 0;
  345.   wc.cbWndExtra = 0;
  346.   wc.hInstance = hInstance;
  347.   wc.hIcon = LoadIcon(hInstance,szAppName);
  348.   wc.hCursor = LoadCursor(NULL,IDC_ARROW);
  349.   wc.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
  350.   wc.lpszMenuName = szAppName;
  351.   wc.lpszClassName = szAppName;
  352.  
  353.   // Register the window class and return success/failure code.
  354.   return(RegisterClass(&wc));
  355. }
  356.  
  357. /////////////////////////////////////////////////////////////////////
  358. // InitInstance
  359. /////////////////////////////////////////////////////////////////////
  360. BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
  361. {
  362.   HWND hwnd;  // Main window handle.
  363.   INT i, j, k;
  364.   RECT rctmp;
  365.   int screenx, screeny;
  366.  
  367.   HRESULT hResult;
  368.   DWORD dwFlags;
  369.   DDBLTFX bltFX; //Blit FX
  370.   DDSCAPS ddsCaps; // Surface capabilities
  371.    
  372.   // Save the instance handle in static variable, which will be
  373.   // used in many subsequent calls from this application to
  374.   // Windows
  375.   hInst = hInstance;  // Store inst handle in our global variable
  376.  
  377.   // Create a main window for this application instance
  378.   DIBWidth = INITIAL_DIB_WIDTH;
  379.   DIBHeight = INITIAL_DIB_HEIGHT;
  380.   rctmp.left = 0;
  381.   rctmp.top = 0;
  382.   rctmp.right = DIBWidth;
  383.   rctmp.bottom = DIBHeight;
  384.  
  385.   AdjustWindowRect(&rctmp,WS_OVERLAPPEDWINDOW,1);
  386.  
  387.   screenx = GetSystemMetrics(SM_CXSCREEN);
  388.   screeny = GetSystemMetrics(SM_CYSCREEN);
  389.  
  390.   hwnd = CreateWindow(
  391.                 szAppName,  // See RegisterClass() call.
  392.                 szTitle,  // Text for window title bar.
  393.                 WS_OVERLAPPEDWINDOW,  // Window style.
  394.                 screenx - (rctmp.right - rctmp.left),
  395.                 screeny - (rctmp.bottom - rctmp.top),
  396.                 rctmp.right - rctmp.left,
  397.                 rctmp.bottom - rctmp.top,
  398.                 NULL,
  399.                 NULL,
  400.                 hInstance,
  401.                 NULL
  402.                 );
  403.  
  404.   // If window could not be created, return "failure"
  405.   if (!hwnd) return(FALSE);
  406.  
  407.   // Make the window visible and draw it
  408.   ShowWindow(hwnd,nCmdShow);  // Show the window
  409.   UpdateWindow(hwnd);  // Sends WM_PAINT message
  410.  
  411.   //Create DirectDraw object.
  412.   hResult = DirectDrawCreate(NULL,&pDirectDraw,NULL);
  413.   if (hResult != DD_OK) return FALSE;
  414.  
  415.   //Set DirectDraw co-operative level.
  416.   hResult = IDirectDraw_SetCooperativeLevel(pDirectDraw, hwnd, DDSCL_EXCLUSIVE | DDSCL_FULLSCREEN);
  417.   if (hResult != DD_OK) return FALSE;
  418.  
  419.   //Set the display mode.
  420.   hResult = IDirectDraw_SetDisplayMode(pDirectDraw, DIBWidth, DIBHeight, 8);
  421.   if (hResult != DD_OK) return FALSE;
  422.  
  423.   //Create DirectDraw surfaces.
  424.   //A complex surface is flipable, and has a back buffer.
  425.   ddSurfaceDesc.dwSize = sizeof(ddSurfaceDesc);
  426.   ddSurfaceDesc.dwFlags = DDSD_CAPS | DDSD_BACKBUFFERCOUNT;
  427.   ddSurfaceDesc.ddsCaps.dwCaps = DDSCAPS_PRIMARYSURFACE | DDSCAPS_COMPLEX | DDSCAPS_FLIP;
  428.   ddSurfaceDesc.dwBackBufferCount = 1; //We only require 1 back buffer.
  429.   hResult = IDirectDraw_CreateSurface(pDirectDraw, &ddSurfaceDesc, &pDDSurface, NULL);
  430.   if (hResult != DD_OK) return FALSE;
  431.   
  432.   //Get a pointer to the back buffer that was created for us
  433.   ddsCaps.dwCaps = DDSCAPS_BACKBUFFER;
  434.   hResult = IDirectDrawSurface_GetAttachedSurface(pDDSurface, &ddsCaps, &pDDBackBuffer);
  435.   if (hResult != DD_OK) return FALSE;
  436.  
  437.   //Create DirectDraw palette (just a normal Windows palette).
  438.   
  439.   // Set up the 6value-6value-6value RGB palette,
  440.   // followed by 20 gray levels, that we want to work with.
  441.   for (i = 0; i < 6; i++)
  442.     for (j = 0; j < 6; j++)
  443.       for (k = 0; k < 6; k++) {
  444.         palDDPalette[i*36 + j*6 + k].peRed = i * 255 / 6;
  445.         palDDPalette[i*36 + j*6 + k].peGreen = j * 255 / 6;
  446.         palDDPalette[i*36 + j*6 + k].peBlue = k * 255 / 6;
  447.         palDDPalette[i*36 + j*6 + k].peFlags = PC_RESERVED | PC_NOCOLLAPSE;
  448.       }
  449.  
  450.   for (i = 0; i < 20; i++) {
  451.     palDDPalette[i+216].peRed = i * 255 / 20;
  452.     palDDPalette[i+216].peGreen = i * 255 / 20;
  453.     palDDPalette[i+216].peBlue = i * 255 / 20;
  454.     palDDPalette[i+216].peFlags = PC_RESERVED | PC_NOCOLLAPSE;
  455.   }
  456.  
  457.   //Create our DirectDraw palette
  458.   hResult = IDirectDraw_CreatePalette(pDirectDraw, DDPCAPS_8BIT, palDDPalette, &pDDPalette, NULL);
  459.   if (hResult != DD_OK) return FALSE;
  460.   
  461.   //Attach our palette to the front buffer (immediate palette change)
  462.   hResult = IDirectDrawSurface_SetPalette(pDDSurface, pDDPalette);
  463.   if (hResult != DD_OK) return FALSE;
  464.  
  465.   // Clear the front and back surfaces
  466.   //Not necessary for this app, but good practise.
  467.   dwFlags = DDBLT_COLORFILL;
  468.   bltFX.dwSize = sizeof(bltFX);
  469.   bltFX.dwFillColor = 0;
  470.   IDirectDrawSurface_Blt(pDDSurface, NULL, NULL, NULL, dwFlags, &bltFX);
  471.   IDirectDrawSurface_Blt(pDDBackBuffer, NULL, NULL, NULL, dwFlags, &bltFX);
  472.  
  473.   // Set the initial location, direction, and speed
  474.   roll = 0.0;
  475.   pitch = 0.0;
  476.   yaw = 0.0;
  477.   currentspeed = 0.0;
  478.   currentpos.v[0] = 0.0;
  479.   currentpos.v[1] = 0.0;
  480.   currentpos.v[2] = 0.0;
  481.   fieldofview = 2.0;
  482.   xscreenscale = DIBWidth / fieldofview;
  483.   yscreenscale = DIBHeight / fieldofview;
  484.   maxscale = max(xscreenscale,yscreenscale);
  485.   maxscreenscaleinv = 1.0 / maxscale;
  486.   xcenter = DIBWidth / 2.0 - 0.5;
  487.   ycenter = DIBHeight / 2.0 - 0.5;
  488.  
  489.   numobjects = sizeof(objects) / sizeof(objects[0]);
  490.  
  491.   return(TRUE);  // We succeeded...
  492. }
  493.  
  494. /////////////////////////////////////////////////////////////////////
  495. // WndProc
  496. /////////////////////////////////////////////////////////////////////
  497. LRESULT CALLBACK WndProc(HWND hwnd, UINT message, WPARAM uParam, LPARAM lParam)
  498. {
  499.   int wmId, wmEvent;
  500.  
  501.   switch (message) {
  502.     case WM_COMMAND:  // message: command from application menu
  503.       wmId = LOWORD(uParam);
  504.       wmEvent = HIWORD(uParam);
  505.  
  506.       switch (wmId) {
  507.         case IDM_EXIT:
  508.           DestroyWindow(hwnd);
  509.           break;
  510.         default:
  511.           return(DefWindowProc(hwnd,message,uParam,lParam));
  512.       }
  513.       break;
  514.  
  515.     case WM_KEYDOWN:
  516.       switch (uParam) {
  517.  
  518.         case VK_DOWN:
  519.           currentspeed -= MOVEMENT_SPEED * speedscale;
  520.           if (currentspeed < -(MAX_MOVEMENT_SPEED * speedscale))
  521.             currentspeed = -(MAX_MOVEMENT_SPEED * speedscale);
  522.           break;
  523.  
  524.         case VK_UP:
  525.           currentspeed += MOVEMENT_SPEED * speedscale;
  526.           if (currentspeed > (MAX_MOVEMENT_SPEED * speedscale))
  527.             currentspeed = (MAX_MOVEMENT_SPEED * speedscale);
  528.           break;
  529.  
  530.         case 'N':
  531.           roll += ROLL_SPEED * speedscale;
  532.           if (roll >= (PI * 2))
  533.             roll -= PI * 2;
  534.           break;
  535.  
  536.         case 'M':
  537.           roll -= ROLL_SPEED * speedscale;
  538.           if (roll < 0)
  539.             roll += PI * 2;
  540.           break;
  541.  
  542.         case 'A':
  543.           pitch -= PITCH_SPEED * speedscale;
  544.           if (pitch < 0)
  545.             pitch += PI * 2;
  546.           break;
  547.  
  548.         case 'Z':
  549.           pitch += PITCH_SPEED * speedscale;
  550.           if (pitch >= (PI * 2))
  551.             pitch -= PI * 2;
  552.           break;
  553.  
  554.         case 'D':
  555.           currentpos.v[1] += VMOVEMENT_SPEED;
  556.           break;
  557.  
  558.         case 'C':
  559.           currentpos.v[1] -= VMOVEMENT_SPEED;
  560.           break;
  561.  
  562.         case VK_LEFT:
  563.           yaw -= YAW_SPEED * speedscale;
  564.           if (yaw < 0)
  565.             yaw += PI * 2;
  566.           break;
  567.  
  568.         case VK_RIGHT:
  569.           yaw += YAW_SPEED * speedscale;
  570.           if (yaw >= (PI * 2))
  571.             yaw -= PI * 2;
  572.           break;
  573.  
  574.         default:
  575.           break;
  576.       }
  577.       return(0);
  578.  
  579.     case WM_KEYUP:
  580.       switch (uParam) {
  581.  
  582.         case VK_ESCAPE:
  583.           //User has pressed 'Esc'
  584.           PostQuitMessage(0);
  585.           break;
  586.  
  587.         case VK_SUBTRACT:
  588.           fieldofview *= 0.9;
  589.           xscreenscale = DIBWidth / fieldofview;
  590.           yscreenscale = DIBHeight / fieldofview;
  591.           maxscale = max(xscreenscale,yscreenscale);
  592.           break;
  593.           
  594.         case VK_ADD:
  595.           fieldofview *= 1.1;
  596.           xscreenscale = DIBWidth / fieldofview;
  597.           yscreenscale = DIBHeight / fieldofview;
  598.           maxscale = max(xscreenscale,yscreenscale);
  599.           break;
  600.  
  601.         case 'F':
  602.           speedscale *= 1.1;
  603.           break;
  604.  
  605.         case 'S':
  606.           speedscale *= 0.9;
  607.           break;
  608.  
  609.         default:
  610.           break;
  611.       }
  612.       return(0);
  613.  
  614.     case WM_SIZE:  // window size changed
  615.       break;
  616.  
  617.     case WM_DESTROY:  // message: window being destroyed
  618.       PostQuitMessage(0);
  619.       break;
  620.       
  621.     case WM_MOUSEMOVE:
  622.       //For future use...
  623.       //mouse_event(MOUSEEVENTF_ABSOLUTE || MOUSEEVENTF_MOVE,0,0,0,0);
  624.       break;
  625.       
  626.     default:  // Passes it on if unproccessed
  627.       return(DefWindowProc(hwnd,message,uParam,lParam));
  628.   }
  629.   return(0);
  630. }
  631.  
  632. /////////////////////////////////////////////////////////////////////
  633. // 3-D dot product.
  634. /////////////////////////////////////////////////////////////////////
  635. double DotProduct(point_t *vec1, point_t *vec2)
  636. {
  637.   return vec1->v[0] * vec2->v[0] + vec1->v[1] * vec2->v[1] +
  638.           vec1->v[2] * vec2->v[2];
  639. }
  640.  
  641. /////////////////////////////////////////////////////////////////////
  642. // 3-D cross product.
  643. /////////////////////////////////////////////////////////////////////
  644. void CrossProduct(point_t *in1, point_t *in2, point_t *out)
  645. {
  646.   out->v[0] = in1->v[1] * in2->v[2] - in1->v[2] * in2->v[1];
  647.   out->v[1] = in1->v[2] * in2->v[0] - in1->v[0] * in2->v[2];
  648.   out->v[2] = in1->v[0] * in2->v[1] - in1->v[1] * in2->v[0];
  649. }
  650.  
  651. /////////////////////////////////////////////////////////////////////
  652. // Concatenate two 3x3 matrices.
  653. /////////////////////////////////////////////////////////////////////
  654. void MConcat(double in1[3][3], double in2[3][3], double out[3][3])
  655. {
  656.   int i, j;
  657.  
  658.   for (i = 0; i < 3; i++)
  659.     for (j = 0; j < 3; j++)
  660.       out[i][j] = in1[i][0] * in2[0][j] + in1[i][1] * in2[1][j] +
  661.                   in1[i][2] * in2[2][j];
  662. }
  663.  
  664. /////////////////////////////////////////////////////////////////////
  665. // Project viewspace polygon vertices into screen coordinates.
  666. // Note that the y axis goes up in worldspace and viewspace, but
  667. // goes down in screenspace.
  668. /////////////////////////////////////////////////////////////////////
  669. void ProjectPolygon(polygon_t *ppoly, polygon2D_t *ppoly2D)
  670. {
  671.   int i;
  672.   double zrecip;
  673.  
  674.   for (i = 0; i < ppoly->numverts; i++) {
  675.     zrecip = 1.0 / ppoly->verts[i].v[2];
  676.     ppoly2D->verts[i].x = ppoly->verts[i].v[0] * zrecip * maxscale + xcenter;
  677.     ppoly2D->verts[i].y = ycenter - (ppoly->verts[i].v[1] * zrecip * maxscale);
  678.   }
  679.   ppoly2D->numverts = ppoly->numverts;
  680. }
  681.  
  682. /////////////////////////////////////////////////////////////////////
  683. // Move the view position and set the world->view transform.
  684. /////////////////////////////////////////////////////////////////////
  685. void UpdateViewPos()
  686. {
  687.   int i;
  688.   point_t motionvec;
  689.   double s, c, mtemp1[3][3], mtemp2[3][3];
  690.  
  691.   // Move in the view direction, across the x-y plane, as if
  692.   // walking. This approach moves slower when looking up or
  693.   // down at more of an angle
  694.   motionvec.v[0] = DotProduct(&vpn,&xaxis);
  695.   motionvec.v[1] = 0.0;
  696.   motionvec.v[2] = DotProduct(&vpn,&zaxis);
  697.  
  698.   for (i = 0; i < 3; i++) {
  699.     currentpos.v[i] += motionvec.v[i] * currentspeed;
  700.     if (currentpos.v[i] > MAX_COORD) currentpos.v[i] = MAX_COORD;
  701.     if (currentpos.v[i] < -MAX_COORD) currentpos.v[i] = -MAX_COORD;
  702.   }
  703.  
  704.   // Set up the world-to-view rotation.
  705.   // Note: much of the work done in concatenating these matrices
  706.   // can be factored out, since it contributes nothing to the
  707.   // final result; multiply the three matrices together on paper
  708.   // to generate a minimum equation for each of the 9 final elements
  709.   s = sin(roll);
  710.   c = cos(roll);
  711.   mroll[0][0] = c;
  712.   mroll[0][1] = s;
  713.   mroll[1][0] = -s;
  714.   mroll[1][1] = c;
  715.  
  716.   s = sin(pitch);
  717.   c = cos(pitch);
  718.   mpitch[1][1] = c;
  719.   mpitch[1][2] = s;
  720.   mpitch[2][1] = -s;
  721.   mpitch[2][2] = c;
  722.  
  723.   s = sin(yaw);
  724.   c = cos(yaw);
  725.   myaw[0][0] = c;
  726.   myaw[0][2] = -s;
  727.   myaw[2][0] = s;
  728.   myaw[2][2] = c;
  729.  
  730.   MConcat(mroll,myaw,mtemp1);
  731.   MConcat(mpitch,mtemp1,mtemp2);
  732.  
  733.   // Break out the rotation matrix into vright, vup, and vpn.
  734.   // We could work directly with the matrix; breaking it out
  735.   // into three vectors is just to make things clearer
  736.   for (i = 0; i < 3; i++) {
  737.     vright.v[i] = mtemp2[0][i];
  738.     vup.v[i] = mtemp2[1][i];
  739.     vpn.v[i] = mtemp2[2][i];
  740.   }
  741.  
  742.   // Simulate crude friction
  743.   if (currentspeed > (MOVEMENT_SPEED * speedscale / 2.0))
  744.     currentspeed -= MOVEMENT_SPEED * speedscale / 2.0;
  745.   else if (currentspeed < -(MOVEMENT_SPEED * speedscale / 2.0))
  746.     currentspeed += MOVEMENT_SPEED * speedscale / 2.0;
  747.   else
  748.     currentspeed = 0.0;
  749. }
  750.  
  751. /////////////////////////////////////////////////////////////////////
  752. // Rotate a vector from viewspace to worldspace.
  753. /////////////////////////////////////////////////////////////////////
  754. void BackRotateVector(point_t *pin, point_t *pout)
  755. {
  756.   int i;
  757.  
  758.   // Rotate into the world orientation
  759.   for (i = 0; i < 3; i++)
  760.     pout->v[i] = pin->v[0] * vright.v[i] + pin->v[1] * vup.v[i] +
  761.                  pin->v[2] * vpn.v[i];
  762. }
  763.  
  764. /////////////////////////////////////////////////////////////////////
  765. // Transform a point from worldspace to viewspace.
  766. /////////////////////////////////////////////////////////////////////
  767. void TransformPoint(point_t *pin, point_t *pout)
  768. {
  769.   int i;
  770.   point_t tvert;
  771.  
  772.   // Translate into a viewpoint-relative coordinate
  773.   for (i = 0; i < 3; i++)
  774.     tvert.v[i] = pin->v[i] - currentpos.v[i];
  775.  
  776.   // Rotate into the view orientation
  777.   pout->v[0] = DotProduct(&tvert,&vright);
  778.   pout->v[1] = DotProduct(&tvert,&vup);
  779.   pout->v[2] = DotProduct(&tvert,&vpn);
  780. }
  781.  
  782. /////////////////////////////////////////////////////////////////////
  783. // Transform a polygon from worldspace to viewspace.
  784. /////////////////////////////////////////////////////////////////////
  785. void TransformPolygon(polygon_t *pinpoly, polygon_t *poutpoly)
  786. {
  787.   int i;
  788.  
  789.   for (i = 0; i < pinpoly->numverts; i++)
  790.     TransformPoint(&pinpoly->verts[i],&poutpoly->verts[i]);
  791.     
  792.   poutpoly->numverts = pinpoly->numverts;
  793. }
  794.  
  795. /////////////////////////////////////////////////////////////////////
  796. // Returns true if polygon faces the viewpoint, assuming a clockwise
  797. // winding of vertices as seen from the front.
  798. /////////////////////////////////////////////////////////////////////
  799. int PolyFacesViewer(polygon_t *ppoly, plane_t *pplane)
  800. {
  801.   int i;
  802.   point_t viewvec;
  803.  
  804.   for (i = 0; i < 3; i++)
  805.     viewvec.v[i] = ppoly->verts[0].v[i] - currentpos.v[i];
  806.  
  807.   // Use an epsilon here so we don't get polygons tilted so
  808.   // sharply that the gradients are unusable or invalid
  809.   if (DotProduct(&viewvec,&pplane->normal) < -0.01)
  810.     return 1;
  811.   else
  812.     return 0;
  813. }
  814.  
  815. /////////////////////////////////////////////////////////////////////
  816. // Set up a clip plane with the specified normal.
  817. /////////////////////////////////////////////////////////////////////
  818. void SetWorldspaceClipPlane(point_t *normal, plane_t *plane)
  819. {
  820.  
  821.   // Rotate the plane normal into worldspace
  822.   BackRotateVector(normal,&plane->normal);
  823.  
  824.   plane->distance = DotProduct(¤tpos,&plane->normal) + CLIP_PLANE_EPSILON;
  825. }
  826.  
  827. /////////////////////////////////////////////////////////////////////
  828. // Set up the planes of the frustum, in worldspace coordinates.
  829. /////////////////////////////////////////////////////////////////////
  830. void SetUpFrustum(void)
  831. {
  832.   double angle, s, c;
  833.   point_t normal;
  834.  
  835.   angle = atan(2.0 / fieldofview * maxscale / xscreenscale);
  836.   s = sin(angle);
  837.   c = cos(angle);
  838.  
  839.   // Left clip plane
  840.   normal.v[0] = s;
  841.   normal.v[1] = 0;
  842.   normal.v[2] = c;
  843.   SetWorldspaceClipPlane(&normal,&frustumplanes[0]);
  844.  
  845.   // Right clip plane
  846.   normal.v[0] = -s;
  847.   SetWorldspaceClipPlane(&normal,&frustumplanes[1]);
  848.  
  849.   angle = atan(2.0 / fieldofview * maxscale / yscreenscale);
  850.   s = sin(angle);
  851.   c = cos(angle);
  852.  
  853.   // Bottom clip plane
  854.   normal.v[0] = 0;
  855.   normal.v[1] = s;
  856.   normal.v[2] = c;
  857.   SetWorldspaceClipPlane(&normal,&frustumplanes[2]);
  858.  
  859.   // Top clip plane
  860.   normal.v[1] = -s;
  861.   SetWorldspaceClipPlane(&normal,&frustumplanes[3]);
  862. }
  863.  
  864. /////////////////////////////////////////////////////////////////////
  865. // Clip a polygon to a plane.
  866. /////////////////////////////////////////////////////////////////////
  867. int ClipToPlane(polygon_t *pin, plane_t *pplane, polygon_t *pout)
  868. {
  869.   int i, j, nextvert, curin, nextin;
  870.   double curdot, nextdot, scale;
  871.   point_t *pinvert, *poutvert;
  872.  
  873.   pinvert = pin->verts;
  874.   poutvert = pout->verts;
  875.  
  876.   curdot = DotProduct(pinvert,&pplane->normal);
  877.   curin = (curdot >= pplane->distance);
  878.  
  879.   for (i = 0; i < pin->numverts; i++) {
  880.     nextvert = (i + 1) % pin->numverts;
  881.  
  882.     // Keep the current vertex if it's inside the plane
  883.     if (curin)  *poutvert++ = *pinvert;
  884.  
  885.     nextdot = DotProduct(&pin->verts[nextvert],&pplane->normal);
  886.     nextin = (nextdot >= pplane->distance);
  887.  
  888.     // Add a clipped vertex if one end of the current edge is
  889.     // inside the plane and the other is outside
  890.     if (curin != nextin) {
  891.       scale = (pplane->distance - curdot) / (nextdot - curdot);
  892.       for (j = 0; j < 3; j++)
  893.         poutvert->v[j] = pinvert->v[j] +
  894.                         ((pin->verts[nextvert].v[j] - pinvert->v[j]) * scale);
  895.       poutvert++;
  896.     }
  897.  
  898.     curdot = nextdot;
  899.     curin = nextin;
  900.     pinvert++;
  901.   }
  902.  
  903.   pout->numverts = poutvert - pout->verts;
  904.   if (pout->numverts < 3) return 0;
  905.  
  906.   return 1;
  907. }
  908.  
  909. /////////////////////////////////////////////////////////////////////
  910. // Clip a polygon to the frustum.
  911. /////////////////////////////////////////////////////////////////////
  912. int ClipToFrustum(polygon_t *pin, polygon_t *pout)
  913. {
  914.   int i, curpoly;
  915.   polygon_t tpoly[2], *ppoly;
  916.  
  917.   curpoly = 0;
  918.   ppoly = pin;
  919.  
  920.   for (i = 0; i < (NUM_FRUSTUM_PLANES - 1); i++) {
  921.     if (!ClipToPlane(ppoly, &frustumplanes[i], &tpoly[curpoly]))
  922.       return 0;
  923.     ppoly = &tpoly[curpoly];
  924.     curpoly ^= 1;
  925.   }
  926.  
  927.   return ClipToPlane(ppoly, &frustumplanes[NUM_FRUSTUM_PLANES-1], pout);
  928. }
  929.  
  930. /////////////////////////////////////////////////////////////////////
  931. // Add the polygon's edges to the global edge table.
  932. /////////////////////////////////////////////////////////////////////
  933. void AddPolygonEdges(plane_t *plane, polygon2D_t *screenpoly)
  934. {
  935.   double distinv, deltax, deltay, slope;
  936.   int i, nextvert, numverts, temp, topy, bottomy, height;
  937.   edge_t *pedge;
  938.  
  939.   numverts = screenpoly->numverts;
  940.  
  941.   // Clamp the polygon's vertices just in case some very near
  942.   // points have wandered out of range due to floating-point
  943.   // imprecision
  944.   for (i = 0; i < numverts; i++) {
  945.     if (screenpoly->verts[i].x < -0.5) screenpoly->verts[i].x = -0.5;
  946.     if (screenpoly->verts[i].x > ((double)DIBWidth - 0.5))
  947.       screenpoly->verts[i].x = (double)DIBWidth - 0.5;
  948.     if (screenpoly->verts[i].y < -0.5) screenpoly->verts[i].y = -0.5;
  949.     if (screenpoly->verts[i].y > ((double)DIBHeight - 0.5))
  950.       screenpoly->verts[i].y = (double)DIBHeight - 0.5;
  951.   }
  952.  
  953.   // Add each edge in turn
  954.   for (i = 0; i < numverts; i++) {
  955.     nextvert = i + 1;
  956.     if (nextvert >= numverts) nextvert = 0;
  957.  
  958.     topy = (int)ceil(screenpoly->verts[i].y);
  959.     bottomy = (int)ceil(screenpoly->verts[nextvert].y);
  960.     height = bottomy - topy;
  961.     if (height == 0) continue;  // doesn't cross any scan lines
  962.     if (height < 0) {
  963.       // Leading edge
  964.       temp = topy;
  965.       topy = bottomy;
  966.       bottomy = temp;
  967.  
  968.       pavailedge->leading = 1;
  969.  
  970.       deltax = screenpoly->verts[i].x - screenpoly->verts[nextvert].x;
  971.       deltay = screenpoly->verts[i].y - screenpoly->verts[nextvert].y;
  972.       slope = deltax / deltay;
  973.  
  974.       // Edge coordinates are in 16.16 fixed point
  975.       pavailedge->xstep = (int)(slope * (float)0x10000);
  976.       pavailedge->x = (int)((screenpoly->verts[nextvert].x +
  977.                      ((float)topy - screenpoly->verts[nextvert].y) *
  978.                      slope) * (float)0x10000);
  979.     }
  980.     else {
  981.       // Trailing edge
  982.       pavailedge->leading = 0;
  983.  
  984.       deltax = screenpoly->verts[nextvert].x - screenpoly->verts[i].x;
  985.       deltay = screenpoly->verts[nextvert].y - screenpoly->verts[i].y;
  986.       slope = deltax / deltay;
  987.  
  988.       // Edge coordinates are in 16.16 fixed point
  989.       pavailedge->xstep = (int)(slope * (float)0x10000);
  990.       pavailedge->x = (int)((screenpoly->verts[i].x +
  991.                      ((float)topy - screenpoly->verts[i].y) * slope) *
  992.                      (float)0x10000);
  993.     }
  994.  
  995.     // Put the edge on the list to be added on top scan
  996.     pedge = &newedges[topy];
  997.     while (pedge->pnext->x < pavailedge->x)
  998.       pedge = pedge->pnext;
  999.     pavailedge->pnext = pedge->pnext;
  1000.     pedge->pnext = pavailedge;
  1001.  
  1002.     // Put the edge on the list to be removed after final scan
  1003.     pavailedge->pnextremove = removeedges[bottomy - 1];
  1004.     removeedges[bottomy - 1] = pavailedge;
  1005.  
  1006.     // Associate the edge with the surface we'll create for
  1007.     // this polygon
  1008.     pavailedge->psurf = pavailsurf;
  1009.  
  1010.     // Make sure we don't overflow the edge array
  1011.     if (pavailedge < &edges[MAX_EDGES]) pavailedge++;
  1012.   }
  1013.  
  1014.   // Create the surface, so we'll know how to sort and draw from
  1015.   // the edges
  1016.   pavailsurf->state = 0;
  1017.   pavailsurf->color = currentcolor;
  1018.  
  1019.   // Set up the 1/z gradients from the polygon, calculating the
  1020.   // base value at screen coordinate 0,0 so we can use screen
  1021.   // coordinates directly when calculating 1/z from the gradients
  1022.   distinv = 1.0 / plane->distance;
  1023.   pavailsurf->zinvstepx = plane->normal.v[0] * distinv *
  1024.                          maxscreenscaleinv * (fieldofview / 2.0);
  1025.   pavailsurf->zinvstepy = -plane->normal.v[1] * distinv *
  1026.                          maxscreenscaleinv * (fieldofview / 2.0);
  1027.   pavailsurf->zinv00 = plane->normal.v[2] * distinv -
  1028.                       xcenter * pavailsurf->zinvstepx -
  1029.                       ycenter * pavailsurf->zinvstepy;
  1030.  
  1031.   // Make sure we don't overflow the surface array
  1032.   if (pavailsurf < &surfs[MAX_SURFS]) pavailsurf++;
  1033. }
  1034.  
  1035. /////////////////////////////////////////////////////////////////////
  1036. // Scan all the edges in the global edge table into spans.
  1037. /////////////////////////////////////////////////////////////////////
  1038. void ScanEdges(void)
  1039. {
  1040.   int x, y;
  1041.   double fx, fy, zinv, zinv2;
  1042.   edge_t *pedge, *pedge2, *ptemp;
  1043.   span_t *pspan;
  1044.   surf_t *psurf, *psurf2;
  1045.  
  1046.   pspan = spans;
  1047.  
  1048.   // Set up the active edge list as initially empty, containing
  1049.   // only the sentinels (which are also the background fill). Most
  1050.   // of these fields could be set up just once at start-up
  1051.   edgehead.pnext = &edgetail;
  1052.   edgehead.pprev = NULL;
  1053.   edgehead.x = -0xFFFF;  // left edge of screen
  1054.   edgehead.leading = 1;
  1055.   edgehead.psurf = &surfstack;
  1056.  
  1057.   edgetail.pnext = NULL;  // mark edge of list
  1058.   edgetail.pprev = &edgehead;
  1059.   edgetail.x = DIBWidth << 16;  // right edge of screen
  1060.   edgetail.leading = 0;
  1061.   edgetail.psurf = &surfstack;
  1062.  
  1063.   // The background surface is the entire stack initially, and
  1064.   // is infinitely far away, so everything sorts in front of it.
  1065.   // This could be set just once at start-up
  1066.   surfstack.pnext = surfstack.pprev = &surfstack;
  1067.   surfstack.color = 0;
  1068.   surfstack.zinv00 = -999999.0;
  1069.   surfstack.zinvstepx = surfstack.zinvstepy = 0.0;
  1070.  
  1071.   for (y = 0; y < DIBHeight; y++) {
  1072.     fy = (double)y;
  1073.  
  1074.     // Sort in any edges that start on this scan
  1075.     pedge = newedges[y].pnext;
  1076.     pedge2 = &edgehead;
  1077.     while (pedge != &maxedge) {
  1078.       while (pedge->x > pedge2->pnext->x)
  1079.         pedge2 = pedge2->pnext;
  1080.  
  1081.       ptemp = pedge->pnext;
  1082.       pedge->pnext = pedge2->pnext;
  1083.       pedge->pprev = pedge2;
  1084.       pedge2->pnext->pprev = pedge;
  1085.       pedge2->pnext = pedge;
  1086.  
  1087.       pedge2 = pedge;
  1088.       pedge = ptemp;
  1089.     }
  1090.  
  1091.     // Scan out the active edges into spans
  1092.  
  1093.     // Start out with the left background edge already inserted,
  1094.     // and the surface stack containing only the background
  1095.     surfstack.state = 1;
  1096.     surfstack.visxstart = 0;
  1097.  
  1098.     for (pedge = edgehead.pnext; pedge; pedge = pedge->pnext) {
  1099.       psurf = pedge->psurf;
  1100.  
  1101.       if (pedge->leading) {
  1102.         // It's a leading edge. Figure out where it is
  1103.         // relative to the current surfaces and insert in
  1104.         // the surface stack; if it's on top, emit the span
  1105.         // for the current top.
  1106.         // First, make sure the edges don't cross
  1107.         if (++psurf->state == 1) {
  1108.           fx = (double)pedge->x * (1.0 / (double)0x10000);
  1109.           // Calculate the surface's 1/z value at this pixel
  1110.           zinv = psurf->zinv00 + psurf->zinvstepx * fx +
  1111.                 psurf->zinvstepy * fy;
  1112.  
  1113.           // See if that makes it a new top surface
  1114.           psurf2 = surfstack.pnext;
  1115.           zinv2 = psurf2->zinv00 + psurf2->zinvstepx * fx +
  1116.                  psurf2->zinvstepy * fy;
  1117.           if (zinv >= zinv2) {
  1118.             // It's a new top surface
  1119.             // emit the span for the current top
  1120.             x = (pedge->x + 0xFFFF) >> 16;
  1121.             pspan->count = x - psurf2->visxstart;
  1122.             if (pspan->count > 0) {
  1123.               pspan->y = y;
  1124.               pspan->x = psurf2->visxstart;
  1125.               pspan->color = psurf2->color;
  1126.  
  1127.               // Make sure we don't overflow
  1128.               // the span array
  1129.               if (pspan < &spans[MAX_SPANS]) pspan++;
  1130.             }
  1131.  
  1132.             psurf->visxstart = x;
  1133.  
  1134.             // Add the edge to the stack
  1135.             psurf->pnext = psurf2;
  1136.             psurf2->pprev = psurf;
  1137.             surfstack.pnext = psurf;
  1138.             psurf->pprev = &surfstack;
  1139.           }
  1140.           else {
  1141.             // Not a new top; sort into the surface stack.
  1142.             // Guaranteed to terminate due to sentinel
  1143.             // background surface
  1144.             do {
  1145.               psurf2 = psurf2->pnext;
  1146.               zinv2 = psurf2->zinv00 + psurf2->zinvstepx * fx +
  1147.                       psurf2->zinvstepy * fy;
  1148.             } while (zinv < zinv2);
  1149.  
  1150.             // Insert the surface into the stack
  1151.             psurf->pnext = psurf2;
  1152.             psurf->pprev = psurf2->pprev;
  1153.             psurf2->pprev->pnext = psurf;
  1154.             psurf2->pprev = psurf;
  1155.           }
  1156.         }
  1157.       }
  1158.       else {
  1159.         // It's a trailing edge; if this was the top surface,
  1160.         // emit the span and remove it.
  1161.         // First, make sure the edges didn't cross
  1162.         if (--psurf->state == 0) {
  1163.           if (surfstack.pnext == psurf) {
  1164.             // It's on top, emit the span
  1165.             x = ((pedge->x + 0xFFFF) >> 16);
  1166.             pspan->count = x - psurf->visxstart;
  1167.             if (pspan->count > 0) {
  1168.               pspan->y = y;
  1169.               pspan->x = psurf->visxstart;
  1170.               pspan->color = psurf->color;
  1171.  
  1172.               // Make sure we don't overflow
  1173.               // the span array
  1174.               if (pspan < &spans[MAX_SPANS]) pspan++;
  1175.             }
  1176.  
  1177.             psurf->pnext->visxstart = x;
  1178.           }
  1179.  
  1180.           // Remove the surface from the stack
  1181.           psurf->pnext->pprev = psurf->pprev;
  1182.           psurf->pprev->pnext = psurf->pnext;
  1183.         }
  1184.       }
  1185.     }
  1186.  
  1187.     // Remove edges that are done
  1188.     pedge = removeedges[y];
  1189.     while (pedge) {
  1190.       pedge->pprev->pnext = pedge->pnext;
  1191.       pedge->pnext->pprev = pedge->pprev;
  1192.       pedge = pedge->pnextremove;
  1193.     }
  1194.  
  1195.     // Step the remaining edges one scan line, and re-sort
  1196.     for (pedge = edgehead.pnext; pedge != &edgetail; ) {
  1197.       ptemp = pedge->pnext;
  1198.  
  1199.       // Step the edge
  1200.       pedge->x += pedge->xstep;
  1201.  
  1202.       // Move the edge back to the proper sorted location,
  1203.       // if necessary
  1204.       while (pedge->x < pedge->pprev->x) {
  1205.         pedge2 = pedge->pprev;
  1206.         pedge2->pnext = pedge->pnext;
  1207.         pedge->pnext->pprev = pedge2;
  1208.         pedge2->pprev->pnext = pedge;
  1209.         pedge->pprev = pedge2->pprev;
  1210.         pedge->pnext = pedge2;
  1211.         pedge2->pprev = pedge;
  1212.       }
  1213.  
  1214.       pedge = ptemp;
  1215.     }
  1216.   }
  1217.  
  1218.   pspan->x = -1;  // mark the end of the list
  1219. }
  1220.  
  1221. /////////////////////////////////////////////////////////////////////
  1222. // Draw all the spans that were scanned out.
  1223. /////////////////////////////////////////////////////////////////////
  1224. void DrawSpans(void)
  1225. {
  1226.   HRESULT hResult;
  1227.   BYTE *pBits;
  1228.   span_t *pspan;
  1229.   LONG ddPitch;
  1230.  
  1231.   //Lock the back buffer so we can draw on it
  1232.   //Note that this locks Windows up as well (until Unlock)
  1233.   hResult = IDirectDrawSurface_Lock(pDDBackBuffer, NULL, &ddSurfaceDesc, DDLOCK_SURFACEMEMORYPTR | DDLOCK_WAIT, NULL);
  1234.   if (hResult != DD_OK) return;
  1235.  
  1236.   pBits = ddSurfaceDesc.lpSurface; //The physical address of the surface
  1237.   ddPitch = ddSurfaceDesc.lPitch;  //Never assume this value!
  1238.  
  1239.   for (pspan = spans; pspan->x != -1; pspan++)
  1240.     memset(pBits + (ddPitch * pspan->y) + pspan->x, pspan->color, pspan->count);
  1241.  
  1242.   IDirectDrawSurface_Unlock(pDDBackBuffer, pBits); //Unlock surface
  1243. }
  1244.  
  1245. /////////////////////////////////////////////////////////////////////
  1246. // Clear the lists of edges to add and remove on each scan line.
  1247. /////////////////////////////////////////////////////////////////////
  1248. void ClearEdgeLists(void)
  1249. {
  1250.   int i;
  1251.  
  1252.   for (i = 0; i < DIBHeight; i++) {
  1253.     newedges[i].pnext = &maxedge;
  1254.     removeedges[i] = NULL;
  1255.   }
  1256. }
  1257.  
  1258. /////////////////////////////////////////////////////////////////////
  1259. // Render the current state of the world to the screen.
  1260. /////////////////////////////////////////////////////////////////////
  1261. void UpdateWorld()
  1262. {
  1263.   HRESULT hResult;
  1264.  
  1265.   polygon2D_t screenpoly;
  1266.   polygon_t *ppoly, tpoly0, tpoly1, tpoly2;
  1267.   convexobject_t *pobject;
  1268.   int i, j, k;
  1269.   plane_t plane;
  1270.   point_t tnormal;
  1271.  
  1272.   UpdateViewPos();
  1273.   SetUpFrustum();
  1274.   ClearEdgeLists();
  1275.   pavailsurf = surfs;
  1276.   pavailedge = edges;
  1277.  
  1278.   // Draw all visible faces in all objects
  1279.   pobject = objecthead.pnext;
  1280.  
  1281.   while (pobject != &objecthead) {
  1282.     ppoly = pobject->ppoly;
  1283.  
  1284.     for (i = 0; i < pobject->numpolys; i++) {
  1285.       // Move the polygon relative to the object center
  1286.       tpoly0.numverts = ppoly[i].numverts;
  1287.       for (j = 0; j < tpoly0.numverts; j++)
  1288.         for (k = 0; k < 3; k++)
  1289.           tpoly0.verts[j].v[k] = ppoly[i].verts[j].v[k] + pobject->center.v[k];
  1290.  
  1291.       if (PolyFacesViewer(&tpoly0,&ppoly[i].plane)) {
  1292.         if (ClipToFrustum(&tpoly0,&tpoly1)) {
  1293.           currentcolor = ppoly[i].color;
  1294.           TransformPolygon(&tpoly1,&tpoly2);
  1295.           ProjectPolygon(&tpoly2,&screenpoly);
  1296.  
  1297.           // Move the polygon's plane into viewspace
  1298.           // First move it into worldspace (object relative)
  1299.           tnormal = ppoly[i].plane.normal;
  1300.           plane.distance = ppoly[i].plane.distance + DotProduct(&pobject->center,&tnormal);
  1301.           // Now transform it into viewspace
  1302.           // Determine the distance from the viewpont
  1303.           plane.distance -= DotProduct(¤tpos,&tnormal);
  1304.           // Rotate the normal into view orientation
  1305.           plane.normal.v[0] = DotProduct(&tnormal,&vright);
  1306.           plane.normal.v[1] = DotProduct(&tnormal,&vup);
  1307.           plane.normal.v[2] = DotProduct(&tnormal,&vpn);
  1308.           AddPolygonEdges(&plane,&screenpoly);
  1309.         }
  1310.       }
  1311.     }
  1312.  
  1313.     pobject = pobject->pnext;
  1314.   }
  1315.  
  1316.   ScanEdges();
  1317.   DrawSpans();
  1318.  
  1319.   //Exchange the front and back buffers
  1320.   hResult = IDirectDrawSurface_Flip(pDDSurface, NULL, NULL);
  1321.   
  1322.   //If we have lost our drawing surfaces then get them back.
  1323.   if (hResult == DDERR_SURFACELOST)
  1324.     IDirectDrawSurface_Restore(pDDSurface);
  1325.  
  1326. }
  1327.